package x.y.z;

import java.util.*;

public class LeetCode_0763 {
    public List<Integer> partitionLabels(String s) {
        Map<Character, Integer> lastIndex = new HashMap<>();
        char[] chs = s.toCharArray();
        for (int i = 0; i < chs.length; i++) {
            lastIndex.put(chs[i], i);
        }
        List<Integer> result = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        int maxIndex = 0;
        for (int i = 0; i < chs.length; i++) {
            sb.append(chs[i]);
            int index = lastIndex.get(chs[i]);
            if (index > maxIndex) {
                maxIndex = index;
            }
            if (i == maxIndex) {
                result.add(sb.length());
                sb.delete(0, sb.length());
                maxIndex = 0;
            }
        }
        return result;
    }
}
